public class GraphColoring {

    // 判断将颜色c分配给顶点v是否安全（即是否与相邻顶点颜色冲突）
    private static boolean isSafe(int[][] graph, int v, int[] color, int c) {
        for (int i = 0; i < graph.length; i++) {
            if (graph[v][i] == 1 && color[i] == c) {
                return false;
            }
        }
        return true;
    }

    private static int graphColoring(int[][] graph, int m, int[] color, int v) {
        int numVertices = graph.length;
        if (v == numVertices) {
            return 1;
        }

        int count = 0;
        for (int c = 0; c < m; c++) {
            if (isSafe(graph, v, color, c)) {
                color[v] = c;
                count += graphColoring(graph, m, color, v + 1);
                color[v] = -1;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 1, 1},
                {1, 0, 0, 0},
                {1, 0, 0, 1},
                {1, 0, 1, 0}
        };
        int m = 3;
        int[] color = new int[graph.length];
        for (int i = 0; i < color.length; i++) {
            color[i] = -1;
        }
        int numSolutions = graphColoring(graph, m, color, 0);
        System.out.println("不同着色方案数: " + numSolutions);
    }
}